package study;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;

public class NextNum {
    public static int[] nextGreaterNum(int[] num1, int[] num2) {
        Deque<Integer> stack = new ArrayDeque<>();
        HashMap<Integer,Integer> map = new HashMap<>();
        if(num1.length == 0){
            return new int[]{};
        }
        int[]  ret = new int[num1.length];
        if(num2.length == 0) {
            for (int i = 0; i < ret.length; i++) {
                ret[i] = -1;
            }
        }
        for(int i=0;i<num2.length;i++){
            while(!stack.isEmpty()&&num2[stack.peek()]<num2[i]){
                int j = stack.pop();
                map.put(num2[j],num2[i]);
            }
            stack.push(i);
        }
        for(int i=0;i<num1.length;i++){
            ret[i] = map.getOrDefault(num1[i],-1);
        }
        return ret;
    }

    //暴力法
    public static int[] nextGreaterNum2(int[] num1, int[] num2) {
        if(num1.length == 0){
            return new int[]{};
        }
        int[]  ret = new int[num1.length];
        if(num2.length == 0) {
            for (int i = 0; i < ret.length; i++) {
                ret[i] = -1;
            }
        }
        for (int i = 0; i < num1.length; i++) {
            ret[i] = -1;
            int num = num1[i];
            int x = 0;
            for (int j = 0; j < num2.length; j++) {
                if(num == num2[j]){
                    x= j;
                    break;
                }
            }
            for (int j = x; j < num2.length; j++) {
                if(num < num2[j]){
                    ret[i] = num2[j];
                    break;
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] num1 = {4,1,2};
        int[] num2 = {1,3,4,2};
        int[] ret = nextGreaterNum(num1, num2);
        int[] ret2 = nextGreaterNum2(num1, num2);
        System.out.println(Arrays.toString(ret));
        System.out.println(Arrays.toString(ret2));
    }
}
